import java.util.*;


public class Main {

    //输入一个字符串，求出该字符串包含的字符合集，按照字母的输入顺p序输出
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            String str = scanner.nextLine();
            String ret = func(str);
            System.out.println(ret);
        }
    }

    public static String func(String str) {
        boolean[] flag = new boolean[150];
        StringBuilder tmp = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char str1 = str.charAt(i);
            if (flag[str1] == false) {
                tmp.append(str1);
                flag[str1] = true;
            }
        }
        return tmp.toString();
    }

    //合并两个有序数组：
    //保证A数组有足够的空间存放B数组的元素，A和B中初始元素数目分别为m和n，A数组的空间大小为m+n
    //不要返回合并数组，将B数组的数据合并到A里面就好了，也无需打印
    //A数组在[0, m - 1]的范围也是有序的
    public void merge(int A[], int m, int B[], int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] <= B[j]) {
                A[k] = B[j];
                k--;
                j--;
            } else {
                A[k] = A[i];
                k--;
                j--;
            }
        }
        while (i >= 0) {
            A[k] = B[j];
            k--;
            j--;
        }
    }

    //逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String x : tokens) {
            if (!isMark(x)) {
                stack.push(Integer.parseInt(x));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (x) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    public boolean isMark(String x) {
        if (x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
            return true;
        } else {
            return false;
        }
    }

    //括号匹配
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {
                if (stack.empty()) {
                    return false;
                } else {
                    char ch2 = stack.peek();
                    if (ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']' || ch2 == '{' && ch == '}') {
                        stack.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }

    //判断栈的压出弹出序列
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() && stack.peek().equals(popA[j])) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }

    //将数组分成三个相等的部分
    //问题地址：https://leetcode.cn/problems/partition-array-into-three-parts-with-equal-sum/
    public boolean canThreePartsEqualSum(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum = sum + arr[i];
        }
        if (sum % 3 != 0) {
            return false;
        }
        int left = 0;
        int leftSum = arr[left];
        int right = arr.length - 1;
        int rightSum = arr[right];
        while (left + 1 < right) {
            if (leftSum == sum / 3 && rightSum == sum / 3) {
                return true;
            }
            if (leftSum != sum / 3) {
                left++;
                leftSum = leftSum + arr[left];
            }
            if (rightSum != sum / 3) {
                right--;
                rightSum = rightSum + arr[right];
            }
        }
        return false;
    }

    //最后一块石头的重量
    public int lastStoneWeight(int[] stones) {
        int index = stones.length - 1;
        for (int i = 0; i < stones.length - 1; i++) {
            Arrays.sort(stones);
            if (stones[index - 1] == 0) {
                break;
            }
            stones[index] -= stones[index - 1];
            stones[index - 1] = 0;
        }
        return stones[index];
    }

    //判断字符串子序列
    public boolean isSubsequence(String S, String T) {
        int lenS = S.length();
        int lenT = T.length();
        int i = 0;
        int j = 0;
        while (i < lenS && j < lenT) {
            if (S.charAt(i) == S.charAt(j)) {
                i++;
                j++;
            } else {
                j++;
            }
        }
        return i == lenS;
    }

    //点击消除
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            Deque<Character> stack = new ArrayDeque<>();
            List<Character> list = new ArrayList<>();
            for (int i = 0; i < str.length(); i++) {
                if (stack.isEmpty() || str.charAt(i) != stack.peek()) {
                    stack.push(str.charAt(i));
                } else {
                    stack.pop();
                }
            }
            if (stack.isEmpty()) {
                System.out.println("0");
            } else {
                while (!stack.isEmpty()) {
                    list.add(stack.pop());
                }
                Collections.reverse(list);
                for (int i = 0; i < list.size(); i++) {
                    System.out.print(i);
                }
            }
        }
    }

    //员工的重要性
    class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    }

    Map<Integer, Employee> hash = new HashMap<>();

    public int getImportance(List<Employee> employees, int id) {
        //首先将所有员工数据置入哈希表中
        for (Employee employee : employees) {
            hash.put(employee.id, employee);
        }
        return importance1(id);
    }

    //进行遍历获得重要性
    public int importance1(int id) {
        Employee employee = hash.get(id);
        int total = employee.importance;
        List<Integer> subordinates = employee.subordinates;
        for (int subId : subordinates) {
            total += importance1(subId);
        }
        return total;
    }

    //找到小镇的法官
    public int findJudge(int n, int[][] trust) {
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];
        for (int[] array : trust) {
            int x = array[0];
            int y = array[1];
            ++inDegree[y];
            ++outDegree[x];
        }
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    //二维网格的迁移
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<Integer> rot = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                rot.add(0);
            }
            ret.add(rot);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int index = (i * n + j + k) % (m * n);
                ret.get(index / n).set(index % n, grid[i][j]);
            }
        }
        return ret;
    }

    //股票价格跨度
    class StockSpanner {
        Stack<Integer> prices;
        Stack<Integer> weight;

        public StockSpanner() {
            prices = new Stack<>();
            weight = new Stack<>();
        }

        public int next(int price) {
            int n = 1;
            while (!prices.empty() && prices.peek() <= price) {
                prices.pop();
                n += weight.pop();
            }
            prices.push(price);
            weight.push(n);
            return n;
        }
    }

    //棒球比赛
    public int calPoints(String[] operations) {
        int sum = 0;
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < operations.length; i++) {
            String ch = operations[i];
            if (ch.equals("C") || ch.equals("+") || ch.equals("D")) {
                if (ch.equals("C")) {
                    stack.pop();
                } else if (ch.equals("+")) {
                    int n = Integer.parseInt(stack.pop());
                    int total = n + Integer.parseInt(stack.peek());
                    stack.push(Integer.toString(n));
                    stack.push(Integer.toString(total));
                } else {
                    int m = Integer.parseInt(stack.peek());
                    stack.push(Integer.toString(m * 2));
                }
            } else {
                stack.push(ch);
            }
        }
        while (!stack.empty()) {
            sum += Integer.parseInt(stack.pop());
        }
        return sum;
    }

    //比较含退格的字符串
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '#' && !stack1.empty()) {
                stack1.pop();
            } else if (s.charAt(i) != '#') {
                stack1.push(s.charAt(i));
            }
        }
        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) == '#' && !stack2.empty()) {
                stack2.pop();
            } else if (t.charAt(i) != '#') {
                stack2.push(t.charAt(i));
            }
        }
        while (!stack1.empty() && !stack2.empty()) {
            if (stack1.pop() != stack2.pop()) {
                return false;
            }
        }
        if (stack1.empty() && stack2.empty()) {
            return true;
        } else {
            return false;
        }
    }

    //分条件出栈(猫狗收容所)
    public ArrayList<Integer> asylum(int[][] ope) {
        LinkedList<int[]> list = new LinkedList<>();
        ArrayList<Integer> ret = new ArrayList<>();
        for (int[] item : ope) {
            if (item[0] == 1) {
                list.add(item);
            } else if (item[0] == 2) {
                if (item[1] == 0) {
                    if (!list.isEmpty()) {
                        int[] animal = list.remove(0);
                        ret.add(animal[1]);
                    }
                } else {
                    for (int i = 0; i < list.size(); i++) {
                        if ((item[1] == 1 && list.get(i)[1] > 0) || (item[1] == -1 && list.get(i)[1] < 0)) {
                            int[] animal = list.remove(i);
                            ret.add(animal[1]);
                            break;
                        }
                    }
                }
            }
        }
        return ret;
    }

    //约瑟夫问题II
    public int getResult(int n) {
        if (n < 1) {
            return -1;
        }
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 2 != 0) {
                list.add(i);
            }
        }
        int round = 3;
        while (list.size() > 1) {
            int last = list.removeLast();
            list.addFirst(last);
            int len = list.size();
            int k = 0;
            for (int i = 1; i <= len; i++) {
                if (i % round != 1) {
                    list.remove(i - 1 - k);
                    k++;
                }
            }
            round++;
        }
        return list.pop();
    }

    //最近的请求次数
    class RecentCounter {
        Queue<Integer> queue;

        public RecentCounter() {
            queue = new ArrayDeque<>();
        }

        public int ping(int t) {
            queue.offer(t);
            while (queue.peek() < t - 3000) {
                queue.poll();
            }
            return queue.size();
        }
    }

    //查找和最小的K对数字
    public List<List<Integer>> kSmallestPairs(int[] num1, int[] num2, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (num1[a[0]] + num2[a[1]] - (num1[b[0]] + num2[b[1]])));
        for (int i = 0; i < Math.min(k, num1.length); i++) {
            heap.add(new int[]{i, 0});
        }
        List<List<Integer>> array = new ArrayList<>();
        while (k-- > 0 && !heap.isEmpty()) {
            int[] pos = heap.poll();
            array.add(Arrays.asList(num1[pos[0]], num2[pos[1]]));
            if (++pos[1] < num2.length) {
                heap.offer(pos);
            }
        }
        return array;
    }
    //车队问题
    public int carFleet(int target, int[] position, int[] speed) {
        int n = speed.length;
        if (n <= 1){
            return n;
        }
        double[][] cars= new double[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = (double)(target - position[i]) / speed[i];
        }
        Arrays.sort(cars, Comparator.comparingDouble(a -> a[0]));
        double maxTime = cars[n - 1][1];
        int ant = 0;
        for (int i = n - 1; i >= 1 ; i--) {
            if (maxTime < cars[i - 1][1]){
                ant++;
                maxTime = cars[i - 1][1];
            }
        }
        ant++;
        return ant;
    }

    //颜色分类
    public void sortColors(int[] num) {
        int left=0,right=num.length-1;
        int i=0;
        while(i<=right){
            if(num[i]==0)
                swap(num,i++,left++);
            else if(num[i]==2)
                swap(num,i,right--);
            else
                i++;
        }
    }
    private void swap(int[] num,int i,int j){
        int temp=num[i];
        num[i]=num[j];
        num[j]=temp;
    }

    //比较版本号
    public int compareVersion(String version1, String version2) {
        int n = version1.length();
        int m = version2.length();
        int i = 0;
        int j = 0;
        while (i < n || j < m){
            int x = 0;
            for (; i < n && version1.charAt(i) != '.'; ++i){
                x = x * 10 + version1.charAt(i) - '0';
            }
            i++;
            int y = 0;
            for (; j < m && version2.charAt(j) != '.'; ++j) {
                y = y * 10 + version2.charAt(j) - '0';
            }
            j++;
            if (x != y){
                return x > y ? 1 : -1;
            }
        }
        return 0;
    }

    //找到K个最接近的元素
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();
        for (int m : arr) {
            list.add(m);
        }
        Collections.sort(list, (a, b) ->{
            if (Math.abs(a - x) != Math.abs(b - x)){
                return Math.abs(a - x) - Math.abs(b - x);
            }
            else {
                return a - b;
            }
        });
        List<Integer> ans = list.subList(0, k);
        Collections.sort(ans);
        return ans;
    }

    //前K个高频单词
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String mun : words) {
            map.put(mun, map.getOrDefault(mun, 0) + 1);
        }
        List<String> str = new ArrayList<>();
        for (Map.Entry<String, Integer> x : map.entrySet()) {
            str.add(x.getKey());
        }
        Collections.sort(str, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return map.get(o1) == map.get(o2) ? o1.compareTo(o2) : map.get(o2) - map.get(o1);
            }
        });
        return str.subList(0, k);
    }

    //同构字符串
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s1 = new HashMap<>();
        Map<Character, Character> t1 = new HashMap<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char x = s.charAt(i);
            char y = t.charAt(i);
            if ((s1.containsKey(x) && s1.get(x) != y) || (t1.containsKey(y) && t1.get(y) != x)){
                return false;
            }
            s1.put(x, y);
            t1.put(y, x);
        }
        return true;
    }

    //两个数组的交集II
    public int[] intersect(int[] num1, int[] num2) {
        if (num1.length < num2.length){
            return intersect(num2, num1);
        }
        Map<Integer, Integer> map = new HashMap<>();
        int len = num1.length;
        for (int i = 0; i < len; i++) {
            map.put(num1[i], map.getOrDefault(num1[i], 0) + 1);
        }
        int[] ret = new int[len];
        int index = 0;
        for (int num : num2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0){
                ret[index++] = num;
                count--;
                if (count > 0){
                    map.put(num, count);
                }
                else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(ret, 0, index);
    }

    //两个数的交集
    public int[] intersection(int[] num1, int[] num2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int num : num1) {
            set1.add(num);
        }
        for (int num : num2) {
            set2.add(num);
        }
        return intersectional(set1, set2);
     }

    private int[] intersectional(Set<Integer> set1, Set<Integer> set2) {
        if (set1.size() > set2.size()){
            return intersectional(set2, set1);
        }
        int[] ret = new int[set1.size()];
        Set<Integer> ran = new HashSet<>();
        for (Integer num : set1) {
            if (set2.contains(num)){
                ran.add(num);
            }
        }
        int i = 0;
        for (Integer num : ran) {
            ret[i++] = num;
        }
        return Arrays.copyOfRange(ret, 0, i);
    }

    //字符串中第一个唯一字符
    public int firstUnitChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1){
                return i;
            }
        }
        return -1;
    }

    //最常见的单词
    public String mostCommonWord(String paragraph, String[] banned) {
        Set<String> set = new HashSet<>();
        for (String x : banned) {
            set.add(x);
        }
        int max = 0;
        int len = paragraph.length();
        StringBuffer sb = new StringBuffer();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i <= len; i++) {
            if (i < len && Character.isLetter(paragraph.charAt(i))){
                sb.append(Character.toLowerCase(paragraph.charAt(i)));
            }
            else if(sb.length() > 0){
                String word = sb.toString();
                if (!set.contains(word)){
                    int frequent = map.getOrDefault(word, 0) + 1;
                    map.put(word, frequent);
                    max = Math.max(max, frequent);
                }
                sb.setLength(0);
            }
        }

        String answer = " ";
        Set<Map.Entry<String, Integer>> set1 = map.entrySet();
        for (Map.Entry<String, Integer> entry : set1) {
            int keyNum = entry.getValue();
            String ret = entry.getKey();
            if (keyNum == max){
                answer = ret;
            }
        }
        return answer;
    }

    //比较字符串最小字母出现次数??
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] count = new int[12];
        for (String s : words) {
            count[f(s)]++;
        }
        for (int i = 9; i >= 1; i--) {
            count[i] += count[i + 1];
        }
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            String s = queries[i];
            res[i] = count[f(s) + 1];
        }
        return res;
    }

    public int f(String s) {
        int cnt = 0;
        char ch = 'z';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c < ch) {
                ch = c;
                cnt = 1;
            } else if (c == ch) {
                cnt++;
            }
        }
        return cnt;
    }

    //无重复字符的最长字串??
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }

    //有效的数独
    public boolean isValidSudoku(char[][] board) {
        int[][] row = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] ret = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    row[i][index]++;
                    columns[j][index]++;
                    ret[i / 3][j / 3][index]++;
                    if (row[i][index] > 1 || columns[j][index] > 1 || ret[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    //存在重复的元素
    public boolean containsDuplicate(int[] num) {
        Arrays.sort(num);
        int n = num.length;
        for (int i = 0; i < n - 1; i++) {
            if (num[i] == num[i + 1]){
                return true;
            }
        }
        return false;
    }

    //存在重复的元素II
    public boolean containsNearbyDuplicate(int[] num, int k){
        Map<Integer, Integer> map = new HashMap<>();
        int n = num.length;
        for (int i = 0; i < n; i++) {
            int ret = num[i];
            if (map.containsKey(ret) && i - map.get(ret) <= k){
                return true;
            }
            map.put(ret, i);
        }
        return false;
    }

    //连续数组
    public int findMaxLength(int[] num) {
        Map<Integer, Integer> map = new HashMap<>();
        int maxLength = 0;
        int count = 0;
        map.put(count, -1);
        int n = num.length;
        for (int i = 0; i < n; i++) {
            int newNum = num[i];
            if (newNum == 1){
                count++;
            }
            else {
                count--;
            }
            if (map.containsKey(count)){
                int index = map.get(count);
                maxLength = Math.max(maxLength, i - index);
            }
            else {
                map.put(count, i);
            }
        }
        return maxLength;
    }

    //找不同
    public char findTheDifference(String s, String t){
        int [] arr = new int[26];
        int n = s.length();
        int m = t.length();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            arr[ch - 'a']++;
        }
        for (int i = 0; i < m; i++) {
            char ch = t.charAt(i);
           arr[ch - 'a']--;
           if (arr[ch - 'a'] < 0){
               return ch;
           }
        }
        return ' ';
    }

























}